package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/04/02 19:17
 **/
public class Day4_2_Num1039 {
    class Solution {
        public int minScoreTriangulation(int[] values) {
            //记忆化回溯
            int[][] memo = new int[50][50];
            return dfs(memo,values,0,values.length-1);
        }
        public int dfs(int[][] memo, int[] v, int l, int r){
            if(l+2>r){
                return 0;
            }
            //恰好能组成一个三角形
            if(l+2==r){
                return v[l]*v[l+1]*v[l+2];
            }
            //判断是否有计算过
            if(memo[l][r]!=0){
                return memo[l][r];
            }
            //记录l,r为底的多边形得分最小值
            int min = Integer.MAX_VALUE;
            for(int k = l+1; k < r; k++){
                min = Math.min(min,dfs(memo,v,l,k)+dfs(memo,v,k,r)+v[l]*v[r]*v[k]);
            }
            //记录当前最小值
            memo[l][r] = min;
            return min;
        }
    }
}